//稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。 
//
// 示例 1： 
//
// 
// 输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], 
//s = "ta"
// 输出：-1
// 说明：不存在返回-1。
// 
//
// 示例 2： 
//
// 
// 输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], 
//s = "ball"
// 输出：4
// 
//
// 提示: 
//
// 
// words的长度在[1, 1000000]之间 
// 
//
// Related Topics 数组 字符串 二分查找 👍 91 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-02 00:10:50
 * @description 面试题 10.05.稀疏数组搜索
 */
public class SparseArraySearchLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SparseArraySearchLcci fun=new SparseArraySearchLcci();
	 	 Solution solution = fun.new Solution();
		solution.findString(new String[]{"DirNnILhARNS hOYIFB", "SM ", "YSPBaovrZBS", "evMMBOf", "mCrS", "oRJfjw gwuo", "xOpSEXvfI"},"mCrS");
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findString(String[] words, String s) {
        int l=0,r=words.length-1;
		while (l<=r){
			while (words[l].equals("")) l++;
			while (words[r].equals("")) r--;
			int m=l+(r-l)/2;
			if(words[m].equals(s)) return m;
			int idx=m;
			if(words[idx].equals("")){
				while (words[idx].equals("")&&idx>=l){
					idx--;
				}
				if(idx==l){
					if(words[idx].equals(s)) return idx;
					idx=m;
					while (words[idx].equals("")&&idx<=r){
						idx++;
					}
				}
				if(idx==r){
					if(words[idx].equals(s)) return idx;
					return -1;
				}
			}
			if(words[idx].equals(s)) return idx;
			if(words[idx].compareTo(s)>0){
				r=idx-1;
			}else {
				l=idx+1;
			}
		}
		return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
